#include<vector>
#include<unordered_map>
using namespace std;
class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        if (matrix.size() < 1) return 0;
        for (int i = 1; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                matrix[i][j] += matrix[i - 1][j];
            }
        }
        int cnt = 0;
        for (int sr = 0; sr < matrix.size(); ++sr) {
            for (int er = sr; er < matrix.size(); ++er) {
                unordered_map<int, int>map;
                map[0] = 1;
                int sum = 0;
                for (int col = 0; col < matrix[0].size(); ++col) {
                    sum += matrix[er][col] - (sr == 0 ? 0 : matrix[sr - 1][col]);
                    if (map.find(sum - target) != map.end())
                        cnt += map[sum - target];
                    ++map[sum];
                }
            }
        }
        return cnt;
    }
};